Termination Proof Script

Consider the TRS R consisting of the rewrite rules
1:    app(app(app(if,true),x),y)  → x
2:    app(app(app(if,false),x),y)  → y
3:    app(app(app(until,p),f),x)  → app(app(app(if,app(p,x)),x),app(app(app(until,p),f),app(f,x)))
There are 6 dependency pairs:
4:    APP(app(app(until,p),f),x)  → APP(app(app(if,app(p,x)),x),app(app(app(until,p),f),app(f,x)))
5:    APP(app(app(until,p),f),x)  → APP(app(if,app(p,x)),x)
6:    APP(app(app(until,p),f),x)  → APP(if,app(p,x))
7:    APP(app(app(until,p),f),x)  → APP(p,x)
8:    APP(app(app(until,p),f),x)  → APP(app(app(until,p),f),app(f,x))
9:    APP(app(app(until,p),f),x)  → APP(f,x)
The approximated dependency graph contains one SCC: {4,5,7-9}.
Tyrolean Termination Tool  (0.06 seconds)   ---  May 3, 2006